package com.shangguigu.stack.exc;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * @author: ZhouBert
 * @date: 2019/10/11
 * @description:	中缀表达式转后缀表达式
 * ps:曾经想琢磨出中缀转后缀的算法步骤，但想了好久没有结果。
 * 然后听韩顺平老师讲：他也是从书上看到的步骤，自己也想不出来。算法的层次，首先是理解伟大的算法并运用。
 * 再有了更多的想法以及坚实的数学基础以后，去设计算法。先度过第一个 层次吧！
 * ——2019年10月11日22:56:15 周兆燃
 *
 * https://blog.csdn.net/Coder_Dacyuan/article/details/79941743
 *
 * 基本计算器（加减乘除括号）核心-中缀转后缀（避免了符号的优先级问题）
 */
public class Infix2suffixExpression {

	/**
	 * 中缀表达式转后缀表达式的步骤
	 * Mine:
	 *
	 * @param exp 表达式字符串用空格进行分割
	 * @return
	 */
	public String infix2suffix(String exp){
		///1.分割元素
		String[] items = exp.split(" ");
		///2.存储结果的列表
		List<String> result=new ArrayList<>();
		///3.操作数栈
		Stack<String> opeStack=new Stack<>();

		for (int i = 0; i < items.length; i++) {
			///判断是否是数字
			if (isDigit(items[i])){
				result.add(items[i]);
			}
			///左括号||空-入栈
			else if (items[i].equals("(")||opeStack.isEmpty()){
				opeStack.push(items[i]);
			}
			///当前操作符优先于栈顶元素-入栈
			else if (getRank(items[i])-getRank(opeStack.peek())>0){
				opeStack.push(items[i]);
			}
			///右括号-出栈到结果列表，知道碰到左括号
			else if (items[i].equals(")")){
				String tempOpe=opeStack.pop();
				while (!tempOpe.equals("(")){
					result.add(tempOpe);
					tempOpe = opeStack.pop();
				}
			}
			///todo:当前操作符不优先于栈顶元素（<=）-出栈输出到结果列表，并循环比较栈顶元素与当前元素
			//else if (getRank(items[i])-getRank(opeStack.peek())<0){
			else {
				///原先错误的写法
//				result.add(items[i]);
//				result.add(opeStack.pop());

				do {
					result.add(opeStack.pop());
				}while (!opeStack.isEmpty()&&!(getRank(items[i])-getRank(opeStack.peek())>0));
				opeStack.push(items[i]);

			}
		}

		while (!opeStack.isEmpty()){
			result.add(opeStack.pop());
		}
		StringBuilder stringBuilder=new StringBuilder();
		for (int i = 0; i < result.size(); i++) {
			stringBuilder.append(result.get(i)+"\t");
		}
		return stringBuilder.toString();
	}

	/**
	 * 获取操作数的等级,越大等级越大
	 * @return
	 */
	public int getRank(String ope){
		int ans=0;
		switch (ope){
			case "*":
			case "/":
				ans=2;break;
			case "+":
			case "-":
				ans=1;break;
			case "(":
				ans=0;break;
		}
		return ans;
	}

	/**
	 * 字符串是否为整型
	 * @param item
	 * @return
	 */
	public boolean isDigit(String item){
		///至少出现一次数字
		return item.matches("\\d+");
	}

	public static void main(String[] args) {
		String exp="( 1 + 3 * 5 ) – 7 / 9";
		String exp2="( 1 + 2 + 3 * 4 ) / 5";
		String exp3="2 * ( 9 + 6 / 3 - 5 ) + 4";
		Infix2suffixExpression entity = new Infix2suffixExpression();

		String rs = entity.infix2suffix(exp);
		String rs2 = entity.infix2suffix(exp2);
		String rs3 = entity.infix2suffix(exp3);
		System.out.println(rs);
		System.out.println(rs2);
		System.out.println(rs3);
	}
}
